Encode string with shortest length

Time: O(N^3) on average; Space: O(N^2); medium

Given a non-empty string, encode the string such that its encoded length is the shortest.

The encoding rule is:

  • k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.

Notes:

  • k will be a positive integer and encoded string will not be empty or have extra space.

  • You may assume that the input string contains only lowercase English letters. The string’s length is at most 160.

  • If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.

Example 1:

Input: s = “aaa”

Output: “aaa”

Explanation:

  • There is no way to encode it such that it is shorter than the input string, so we do not encode it.

Example 2:

Input: s = “aaaaa”

Output: “5[a]”

Explanation:

  • “5[a]” is shorter than “aaaaa” by 1 character.

Example 3:

Input: s = “aaaaaaaaaa”

Output: “10[a]”

Explanation:

  • “a9[a]” or “9[a]a” are also valid solutions, both of them have the same length = 5, which is the same as “10[a]”.

Example 4:

Input: s = “aabcaabcd”

Output: “2[aabc]d”

Explanation:

  • “aabc” occurs twice, so one answer can be “2[aabc]d”.

Example 5:

Input: s = “abbbabbbcabbbabbbc”

Output: “2[2[abbb]c]”

Explanation:

  • “abbbabbbc” occurs twice, but “abbbabbbc” can also be encoded to “2[abbb]c”, so one answer can be “2[2[abbb]c]”.

[8]:

class Solution1(object):
    """
    Time: O(N^3) on average
    Space: O(N^2)
    """
    def encode(self, s):
        """
        :type s: str
        :rtype: str
        """
        def encode_substr(dp, s, i, j):
            temp = s[i:j + 1]
            pos = (temp + temp).find(temp, 1)      # O(n) on average
            if pos >= len(temp):
                return temp
            return str(len(temp)//pos) + '[' + dp[i][i + pos - 1] + ']'

        dp = [["" for _ in range(len(s))] for _ in range(len(s))]

        for length in range(1, len(s) + 1):

            for i in range(len(s) + 1-length):
                j = i + length-1
                dp[i][j] = s[i:i + length]

                for k in range(i, j):
                    if len(dp[i][k]) + len(dp[k + 1][j]) < len(dp[i][j]):
                        dp[i][j] = dp[i][k] + dp[k + 1][j]

                encoded_string = encode_substr(dp, s, i, j)

                if len(encoded_string) < len(dp[i][j]):
                    dp[i][j] = encoded_string

        return dp[0][len(s) - 1]

[14]:

sol = Solution1()

s = "aaa"
assert sol.encode(s) == "aaa"
s = "aaaaa"
assert sol.encode(s) == "5[a]"
# s = "aaaaaaaaaa"
# print(sol.encode(s))    # a9[a], not 10[a]?
s = "aaaaaaaaaaa"
assert sol.encode(s) == "11[a]"
s = "aabcaabcd"
assert sol.encode(s) == "2[aabc]d"
s = "abbbabbbcabbbabbbc"
assert sol.encode(s) == "2[2[abbb]c]"